//给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差 
//
// 
//
// 示例： 
//
// 
//输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
//输出：3，即数值对(11, 8)
// 
//
// 
//
// 提示： 
//
// 
// 1 <= a.length, b.length <= 100000 
// -2147483648 <= a[i], b[i] <= 2147483647 
// 正确结果在区间 [0, 2147483647] 内 
// 
//
// Related Topics 数组 双指针 二分查找 排序 👍 92 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.BitSet;

/**
 * @author ldltd
 * @date 2025-09-06 13:38:57
 * @description 面试题 16.06.最小差
 */
public class SmallestDifferenceLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 SmallestDifferenceLcci fun=new SmallestDifferenceLcci();
	 	 Solution solution = fun.new Solution();

	 }

//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 最一般的情况，双重循环，O(N*M)
	// 先排序，然后双指针，O(NlogN + MlogM)
		 public int smallestDifference3(int[] a, int[] b) {
			 java.util.Arrays.sort(a);
			 java.util.Arrays.sort(b);
			 int i = 0, j = 0;
			 int ans = Integer.MAX_VALUE;
			 while (i < a.length && j < b.length) {
				 ans = Math.min(ans, Math.abs(a[i] - b[j]));
				 if (a[i] < b[j]) {
					 i++;
				 } else {
					 j++;
				 }
			 }
			 return ans;

		 }
		 // 2. 哈希表，O(N+M)，空间复杂度O(N+M)
		 public int smallestDifference1(int[] a, int[] b) {
			 java.util.HashSet<Integer> setA = new java.util.HashSet<>();
			 java.util.HashSet<Integer> setB = new java.util.HashSet<>();
			 for (int num : a) {
				 setA.add(num);
			 }
			 for (int num : b) {
				 setB.add(num);
			 }
			 int ans = Integer.MAX_VALUE;
			 for (int num : a) {
				 if (setB.contains(num)) {
					 return 0;
				 }
				 // 找到大于等于num的最小值
				 Integer ceiling = setB.stream().filter(x -> x > num).min(Integer::compareTo).orElse(null);
				 if (ceiling != null) {
					 ans = Math.min(ans, Math.abs(num - ceiling));
				 }
				 // 找到小于等于num的最大值
				 Integer floor = setB.stream().filter(x -> x < num).max(Integer::compareTo).orElse(null);
				 if (floor != null) {
					 ans = Math.min(ans, Math.abs(num - floor));
				 }
			 }
			 for (int num : b) {
				 if (setA.contains(num)) {
					 return 0;
				 }
				 // 找到大于等于num的最小值
				 Integer ceiling = setA.stream().filter(x -> x > num).min(Integer::compareTo).orElse(null);
				 if (ceiling != null) {
					 ans = Math.min(ans, Math.abs(num - ceiling));
				 }
				 // 找到小于等于num的最大值
				 Integer floor = setA.stream().filter(x -> x < num).max(Integer::compareTo).orElse(null);
				 if (floor != null) {
					 ans = Math.min(ans, Math.abs(num - floor));
				 }
			 }
			 return ans;

		 }
		 // 3.  二分查，O(NlogM + MlogM)，空间复杂度O(1)
		 public int smallestDifference(int[] a, int[] b) {
			 java.util.Arrays.sort(b);
			 long minDiff = Long.MAX_VALUE;

			 for (int num : a) {
				 int idx = java.util.Arrays.binarySearch(b, num);
				 if (idx >= 0) {
					 return 0;
				 } else {
					 // 二分查找的结果是-(插入点)-1
					 idx = -idx - 1;
					 if (idx < b.length) {
						 // 使用 long 避免溢出
						 long diff1 = Math.abs((long) num - (long) b[idx]);
						 minDiff = Math.min(minDiff, diff1);
					 }
					 if (idx > 0) {
						 // 使用 long 避免溢出
						 long diff2 = Math.abs((long) num - (long) b[idx - 1]);
						 minDiff = Math.min(minDiff, diff2);
					 }
				 }
			 }
			 return (int) minDiff;
		 }
	// 4. 位图法，O(N+M)，空间复杂度O(K)，K是数值范围，内存可能不够
	public int smallestDifference4(int[] a, int[] b) {
		// 找到最小值和最大值来确定位图范围
		long minVal = Long.MAX_VALUE;
		long maxVal = Long.MIN_VALUE;

		for (int num : a) {
			minVal = Math.min(minVal, num);
			maxVal = Math.max(maxVal, num);
		}
		for (int num : b) {
			minVal = Math.min(minVal, num);
			maxVal = Math.max(maxVal, num);
		}

		// 创建位图（这里会有内存问题！）
		long range = maxVal - minVal + 1;
		if (range > Integer.MAX_VALUE) {
			// 范围太大，回退到排序方法
			return smallestDifferenceFallback(a, b);
		}

		BitSet bitmap = new BitSet((int) range);

		// 标记数组a中的元素
		for (int num : a) {
			bitmap.set((int) (num - minVal));
		}

		// 检查数组b中的元素
		int minDiff = Integer.MAX_VALUE;
		for (int num : b) {
			int pos = (int) (num - minVal);
			if (bitmap.get(pos)) {
				return 0; // 找到完全相同的数
			}

			// 向前查找最近的设置位
			int prev = bitmap.previousSetBit(pos);
			if (prev != -1) {
				minDiff = Math.min(minDiff, pos - prev);
			}

			// 向后查找最近的设置位
			int next = bitmap.nextSetBit(pos);
			if (next != -1) {
				minDiff = Math.min(minDiff, next - pos);
			}
		}

		return minDiff;
	}

	private int smallestDifferenceFallback(int[] a, int[] b) {
		Arrays.sort(a);
		Arrays.sort(b);
		int i = 0, j = 0;
		long minDiff = Long.MAX_VALUE;

		while (i < a.length && j < b.length) {
			long diff = Math.abs((long) a[i] - (long) b[j]);
			minDiff = Math.min(minDiff, diff);
			if (a[i] < b[j]) {
				i++;
			} else {
				j++;
			}
		}
		return (int) minDiff;
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
